package javaapplication2;


// Interface:
// DGBI (constructor)  O(n)
// cantidadCruces() O(1) si no se tocó el dibujo, si se tocó tenemos #V1*#V1*(#V1*#V2)=(#V1)^3*#V2
//  SI #V1+#V2= N
// ENTONCES #V1=N-#V2
// (N-#V2)^3*#V2  EL PEOR CASO ES CUANDO #V2=1, ENTONCES TENEMOS UNA COMPLEJIDAD DE O(N^3) PARA BUSCAR TODOS LOS 
// CRUCES LA PRIMERA VEZ.

public class DGBI {
    // Miembros
    private grafo g;
    private Integer[] V1;
    private Integer[] V2;
    private Integer[] posicionV1;
    private Integer[] posicionV2;
    private int cruces;
    private boolean actualizado;
    // Métodos
    // Constructor
    DGBI(Integer[] v1, Integer[] v2, Eje[] ejes)
    {
        int l1=v1.length;
        int l2= v2.length;
        g = new grafo(l2+l1, false);
        V1=v1;
        V2=v2;
        int e=0;
        while (e<ejes.length)
        {
            g.insert(ejes[e]);
            e++;
        }
        // Armo los arreglos que me dicen la posicion de cada vertice en el dibujo.
        posicionV1=new Integer[l1];
        posicionV2=new Integer[l2];
        int i=0;
        while (i<l1)
        {
            posicionV1[V1[i]]=i;
            i++;
        }
        i=0;
        while (i<l2)
        {
            posicionV2[V2[i]-l1]=i;
            i++;
        }
        cruces=cantidadCruces();
        actualizado=true;
    }
    public int cantidadCruces()
    {
        if (!actualizado)
        {
            cruces=0; // Me preparo para contar..
            // Recorro todos los vértices y analizo cuales vertices de la otra particion tienen ejes que se cruzan
            int v=0;
            while (v<V1.length)
            {
                Integer[] adytsv1 = g.adyacentes(V1[v].intValue()); //Obtengo los ejes adyacentes al vertice
                int nroEje=0;  // Contador para ir analizando los ejes.
                while (nroEje<adytsv1.length)
                {
                    // Recorro los ejes de todos los vertices siguientes al elegido
                    int vertice2=v+1;
                    while (vertice2<V1.length)
                    {
                        Integer[] adytsv2 = g.adyacentes(V1[vertice2].intValue());
                        int looper=0;
                        Integer verticeAux;
                        while (looper<adytsv2.length)
                        {
                            verticeAux=adytsv2[looper];
                            if (posicionV2[verticeAux.intValue()-V1.length]<posicionV2[adytsv1[nroEje].intValue()-V1.length])
                            {
                                cruces++;
                            }
                            looper++;
                        }
                        vertice2++;
                    }
                    nroEje++;
                }
                v++;
            }
        }
        actualizado=true;
        return cruces;
    }
    
    public int CantCortesAfterSwapV1(int PosNodoA, int PosNodoB)
    {
    	int crucesActual = cruces;
		crucesActual = crucesActual - CortesDeV1(PosNodoA);
		crucesActual = crucesActual - CortesDeV1(PosNodoB);
        SwapV1(PosNodoA,PosNodoB);
        crucesActual = crucesActual + CortesDeV1(PosNodoA);
        crucesActual = crucesActual + CortesDeV1(PosNodoB);
        SwapV1(PosNodoA,PosNodoB);
        return crucesActual; 
	}
    	
    public void ConfirmarSwapV1(int PosNodoA, int PosNodoB)
    {
    	SwapV1(PosNodoA,PosNodoB);
    	actualizado=true;
    }
    
	private int CortesDeV1(int PosNodo)
	{
		int crucesDe = 0;
		Integer[] adytsv1 = g.adyacentes(V1[PosNodo].intValue()); //Obtengo los ejes adyacentes al vertice
        int nroEje=0;  // Contador para ir analizando los ejes.
        while (nroEje<adytsv1.length)
        {
            // Recorro los ejes de todos los vertices siguientes al elegido
            int vertice2=PosNodo+1;
            while (vertice2<V1.length)
            {
                Integer[] adytsv2 = g.adyacentes(V1[vertice2].intValue());
                int looper=0;
                Integer verticeAux;
                while (looper<adytsv2.length)
                {
                    verticeAux=adytsv2[looper];
                    if (posicionV2[verticeAux.intValue()-V1.length]<posicionV2[adytsv1[nroEje].intValue()-V1.length])
                    {
                    	crucesDe++;
                    }
                    looper++;
                }
                vertice2++;
            }
            nroEje++;
        }
        return crucesDe;
	}
        
	public int CantCortesAfterSwapV2(int PosNodoA, int PosNodoB)
    {
    	int crucesActual = cruces;
		crucesActual = crucesActual - CortesDeV2(PosNodoA);
		crucesActual = crucesActual - CortesDeV2(PosNodoB);
        SwapV1(PosNodoA,PosNodoB);
        crucesActual = crucesActual + CortesDeV2(PosNodoA);
        crucesActual = crucesActual + CortesDeV2(PosNodoB);
        SwapV1(PosNodoA,PosNodoB);
        return crucesActual; 
	}
    	
    public void ConfirmarSwapV2(int PosNodoA, int PosNodoB)
    {
    	SwapV2(PosNodoA,PosNodoB);
    	actualizado=true;
    }
    
	private int CortesDeV2(int PosNodo)
	{
		int crucesDe = 0;
		Integer[] adytsv2 = g.adyacentes(V2[PosNodo].intValue()); //Obtengo los ejes adyacentes al vertice
        int nroEje=0;  // Contador para ir analizando los ejes.
        while (nroEje<adytsv2.length)
        {
            // Recorro los ejes de todos los vertices siguientes al elegido
            int vertice2=PosNodo+1;
            while (vertice2<V2.length)
            {
                Integer[] adytsv1 = g.adyacentes(V2[vertice2].intValue());
                int looper=0;
                Integer verticeAux;
                while (looper<adytsv1.length)
                {
                    verticeAux=adytsv1[looper];
                    if (posicionV1[verticeAux.intValue()]<posicionV1[adytsv2[nroEje].intValue()])
                    {
                    	crucesDe++;
                    }
                    looper++;
                }
                vertice2++;
            }
            nroEje++;
        }
        return crucesDe;
	}
	
	
    public void SwapV1(int a, int b)
    {
    	Integer aAfterSwap = V1[a];
    	V1[a] = V1[b];
    	V1[b] = aAfterSwap;
    }

    public void SwapV2(int a, int b)
    {
    	Integer aAfterSwap = V2[a];
    	V2[a] = V2[b];
    	V2[b] = aAfterSwap;
    }
    
    
}
